package com.example.algorithm.hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/7/25
 */
public class ThreeCount {


    /**
     * 这里以i为起点，每次只判断i+l和len之间的数
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list=new ArrayList<>();
        Arrays.sort(nums);
        int len=nums.length;
        for(int i=0;i<len;i++)
        {
            //数组已经排好序了，当数组大于0时，则以后的数组都是大于0，没必要再循环了
            if(nums[i]>0)
            {
                return list;
            }
            //过滤掉重复的开头
            if(i>0&&nums[i]==nums[i-1])
            {
                continue;
            }
            int left=i+1;
            int right=len-1;
            while(left<right)
            {
                int sum=nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }else if(sum<0){
                    left++;
                }else {
                    list.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    //过滤掉相同的元素
                    while(left<right&&nums[right]==nums[right-1])
                    {
                        right--;
                    }
                    while(left<right&&nums[left]==nums[left+1])
                    {
                        left++;
                    }
                    left++;
                    right++;
                }

            }
        }
        return list;
    }

    public static void main(String[] args) {

    }
}
